Step 3: The bubble_down(i) Helper

This is the helper for pop. When we move a "wrong" element to the root, bubble_down sinks it to its correct place.

Guidance for Step 3

  • Child Indices: Fill in the left_child and right_child formulas.
  • Find Largest: The code finds the largest among the parent (`i`), left child, and right child. Your blanks are to update largest to the child's index if that child is larger.
  • Critical Check: Notice the left_child < size check. This prevents an `IndexError`.
  • Recursive Call: If a swap happens, you must continue bubbling down from the largest index (which is where your element just moved to). 
# ... (inside PriorityQueue class) ...

    def bubble_down(self, i):
        """
        Recursively moves the element at index 'i' down the heap to
        restore the max-heap property.
        """
        size = len(self.heap)
        
        # 1. Find child indices
        left_child = ________
        right_child = ________
        
        # 2. Find the largest among parent and children
        largest = i
        
        # Check if the left child exists and is larger
        if left_child < size and self.heap[left_child] > self.heap[largest]:
            largest = ________
            
        # Check if the right child exists and is larger
        if right_child < size and self.heap[right_child] > self.heap[largest]:
            largest = ________

        # 3. Base Case: If 'i' is already the largest, it's in the right spot.
        if largest == i:
            return

        # Recursive Step: Swap with the largest child and continue
        self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
        self.bubble_down(________)
Copied!